// 题目描述
// 21. 合并两个有序链表
// 难度
// 简单
// 3189
// 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//   示例 1：
// 输入：l1 = [1,2,4], l2 = [1,3,4]
// 输出：[1,1,2,3,4,4]
// 示例 2：
// 输入：l1 = [], l2 = []
// 输出：[]
// 示例 3：
// 输入：l1 = [], l2 = [0]
// 输出：[0]
//   提示：
// 两个链表的节点数目范围是 [0, 50]
// -100 <= Node.val <= 100
// l1 和 l2 均按 非递减顺序 排列
// 通过次数1,425,716提交次数2,155,010
// https://leetcode.cn/problems/merge-two-sorted-lists/

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  // 链表题目创建哨兵节点是固定套路
  const dummy = new ListNode('#')
  let tail = dummy

  // 尾插法 + 归并排序解决
  let p = list1
  let q = list2
  while (p && q) {
    let cloned = null

    if (p.val <= q.val) {
      cloned = p
      p = p.next
    } else {
      cloned = q
      q = q.next
    }

    tail.next = cloned
    tail = cloned
  }

  // 处理剩余内容，将其直接接入要返回链表的尾部
  if (p) {
    tail.next = p
  } else if (q) {
    tail.next = q
  }

  // 去除掉哨兵节点
  return dummy.next
}
